package com.example.leetcode.leetcode.hot100;

/**
 * @author haitao
 * @date 2021/11/4 2:41 下午
 * 不同的二叉搜索树
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 * n =3
 * 1      1       2        3     3
 * \      \     / \      /     /
 * 3      2   1   3    2     1
 * /       \           /       \
 * 2         3         1         2
 * <p>
 * G[N] 表示n个数字组成的二叉搜索树个数
 * F[i.N]表示从以i为节点，可以组成的二叉搜索树个数
 * 如果G[2] = F[1,2] + F[2,2]
 * 而求F[i,N]，需要知道i-1的二叉搜索树个数和n-i的二叉搜索树个数（只关注个数，不关注i+1到n的自然数大小）
 * F[i,N] = G[i-1] * G[N-i]
 */
public class Solution96 {
    public int numTrees(int n) {
        int[] G = new int[n+1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <=n; i++) {
            for (int j = 1; j<=i; j++) {
                G[i]+= G[j-1]*G[i-j];
            }
        }
        return G[n];
    }
}
